
var max = 1000000;
var pointSet = [];
// 根据图分析 写出 距离的数据结构
// 表示一张图 点集合，边集合 
// 举例 [a,b,c,d,e] 数组点集合
// 可以先画个表格
//   a    b   c   d    e
// a 0    4   7   max  max
// b 4    0   8   6    max
// c 7    8   0   5    max
// d max  6   5    0    7
// e max  max  max   7   0
// 分析出来是个 二维数组
var distance = [
    [0, 4, 7, max, max], // a 到 其他点距离 a b c d e
    [4, 0, 8, 6, max], // b 到其他点距离 a b  c d e
    [7, 8, 0, 5, max], // c 到其他点距离 a b c d e
    [max, 6, 5, 0, 7],// d -> a b c d e 
    [max, max, max, 7, 0]//  e -> a b c d e
];

function Node(value) {
    this.value = value;
    this.neighbor = [];
}

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");

pointSet.push(a);
pointSet.push(b);
pointSet.push(c);
pointSet.push(d);
pointSet.push(e);
// 获取index
function getIndex(str) {
  for (var i = 0 ; i < pointSet.length ; i ++) {
      if (str == pointSet[i].value) return i;
  }
  return -1;
}

//需要传入点的集合，边的集合，当前已经连接进入的集合
// 此方法，根据当前已经有的节点，来进行判断，获取到距离最短的点
function getMinDisNode(pointSet, distance, nowPointSet) {
    let fromNode = null
    let minDis = 1000000
    let minNode = null
    // let 
    console.log(nowPointSet)

    for(let i =0;i<nowPointSet.length;i++){
      console.log(`执行${i}次`+nowPointSet[i].value)
      console.log(nowPointSet[i])
  
      if(!nowPointSet[i]) return;
      let nowIndex = getIndex(nowPointSet[i].value)
      console.log(nowIndex)
      
      for(let j =0;j<distance[nowIndex].length;j++){
        let thisNode = pointSet[j]
        if(nowPointSet.indexOf(thisNode) < 0 && distance[nowIndex][j] < minDis){
              minDis = distance[nowIndex][j]
              fromNode = nowPointSet[i]
              minNode = thisNode
        }
      }
    }
    fromNode.neighbor.push(minNode)
    minNode.neighbor.push(fromNode)
    return minNode
}

function prim(pointSet, distance, start) {
  if(pointSet == null || pointSet.length == 0)return[]
  let newPoint = []
  newPoint[0]=pointSet[0]
  let index = 0
  while(true){
    index++
    let minNode = getMinDisNode(pointSet,distance,newPoint)
    console.log(newPoint[newPoint.length-1])
    console.log(index)
    newPoint.push(minNode)
    if(newPoint.length == pointSet.length)break;
    
  }
  console.log(newPoint)
  // pointSet = newPoint
  return newPoint
}

// prim(pointSet, distance, pointSet[0]);

// console.log(prim(pointSet, distance, pointSet[0]));
// console.log(pointSet)

// 有向 无环 
// 普里姆算法（加点法）prim
// 1.任选一个点作为起点
// 2. 找到以当前选中点为起点路径最短的边
// 3. 如果这个边的另一端没有被联通进来，那么就连结
// 4. 如果这个边的另一端也早就被连进来了，则看倒数第二短的边
// 5. 重复2-4直到所有的点联通为止



// 克鲁斯卡尔算法（加边法） 
// 1.选择最短的边进行连接
// 2. 要保证边连接的两端至少一个点是新的点
// 3.或者这个边是将两个部落进行连接的 如何理解部落 举例： 2个已连接的点 称为一个部落


function kruskal (poinitSet,distance){
  let  tribeList = []//部落
  // let begin = null;
  // let end = null;
 
  for(let i =0;i<poinitSet.length;i++){
    // let map = new Map()
    let minDis= 9999999;
    let thisNode = poinitSet[i]
    if(tribeList.indexOf(thisNode) < 0){
      if( tribeList.length == 0){
        tribeList.push(thisNode)
        console.log('初始值',)
      }
      
    }
    let minDisNode = null
    for(let j = i ; j<distance[i].length;j++){
      
      let disThisNode = poinitSet[j]
      console.log(thisNode,disThisNode,'disThisNode',distance[i][j])
      if(thisNode != disThisNode && minDis > distance[i][j]){
            minDis = distance[i][j]
            minDisNode = disThisNode
            // console.log('minDisNode',minDisNode )
            // map.set(distance[i][j],poinitSet[j])
      }

    }
    //minDis 最小的
    // const islink = isLinkFunc(tribeList,thisNode,minDisNode)
    console.log('minDisNode',minDisNode )
    if(minDisNode){
      console.log(tribeList)
    console.log('xxxx',tribeList.indexOf(minDisNode),thisNode)
    debugger
    if(tribeList.indexOf(minDisNode) != -1){
        if(tribeList.indexOf(thisNode) == -1){
          thisNode.neighbor.push(minDisNode)
          minDisNode.neighbor.push(thisNode)
            
            tribeList.push(thisNode)
            
         
        }
        
    }else{
      thisNode.neighbor.push(minDisNode)
      minDisNode.neighbor.push(thisNode)
      tribeList.push(minDisNode)
    }
   
  }
  console.log('0000000',tribeList)
  debugger
    // 判断最小的点
  }
  return tribeList
}
// kruskal(pointSet,distance)
// debugger


// 理解真正的思路我们再写下
function canLink(begin,end,resultList) {
    if(resultList.length == 0)return true;
    var beginArr = null;
    var endArr = null;
  
    for(let i =0 ;i<resultList.length;i++){
      if(resultList[i].indexOf(begin) != -1){
        beginArr=resultList[i]
      }
      if(resultList[i].indexOf(end) != -1){
        endArr=resultList[i]
      }
    }
    if(beginArr != null && endArr != null && beginArr == endArr)  return false;
    
    

      return true
  
}
function link(begin,end,resultList) {
  if(resultList.length == 0){
    begin.neighbor.push(end)
  end.neighbor.push(begin)
    return resultList.push([begin,end])
  }
  let beginArr = null;
  let endArr = null;
  for(let i =0 ;i<resultList.length;i++){
    if(resultList[i].indexOf(begin) != -1){
      beginArr=resultList[i]
    }
    if(resultList[i].indexOf(end) != -1){
      endArr=resultList[i]
    }
  }
  // if(beginArr != null && endArr != null && beginArr == endArr) return false;
  begin.neighbor.push(end)
  end.neighbor.push(begin)
  if(beginArr == null && endArr == null){
    let newArr = new Array(2)
    newArr[0] = begin
    newArr[1] = end
    resultList.push(newArr)
    
  }else if(beginArr == null && endArr != null){
    let index = resultList.indexOf(endArr)
    // resultList.splice(index,1)
   
    endArr.push(begin)
    resultList[index] = endArr
   

  }else if(beginArr != null && endArr == null){
  
    let index = resultList.indexOf(beginArr)
    // resultList.splice(index,1)
    beginArr.push(end)
    // endArr.push(begin)
    resultList[index] = beginArr
  }else if(beginArr != null && endArr != null && beginArr != endArr){
    let newArr = beginArr.concat(endArr)
    let index = resultList.indexOf(endArr)
    // resultList.splice(index,1)
    resultList[index] = newArr

  }
  

}
function kruskalNew(poinitSet,distance){

  let resultList = []
  
  for(let i = 0;i < distance.length;i++){
    let minDis = max
    let beginNode = poinitSet[i]
    let endNode = null
    for(let j = 0;j<distance[i].length;j++){
      
      let thisEndNode = poinitSet[j]
      console.log(resultList)
      console.log(canLink(beginNode,thisEndNode,resultList))
      if(i !=j
        && minDis > distance[i][j]
        && canLink(beginNode,thisEndNode,resultList)
        ){
            minDis = distance[i][j]
            endNode = thisEndNode
        }
    }
   if(endNode != null) {
    console.log('beginNode',beginNode,'endNode',endNode)
    link(beginNode,endNode,resultList)
   }
   
  }

}
console.log(pointSet)

kruskalNew(pointSet,distance)
console.log(pointSet)
